/*
 * @lc app=leetcode.cn id=22 lang=cpp
 *
 * [22] 括号生成
 *
 * https://leetcode.cn/problems/generate-parentheses/description/
 *
 * algorithms
 * Medium (77.55%)
 * Likes:    2846
 * Dislikes: 0
 * Total Accepted:    580.8K
 * Total Submissions: 749K
 * Testcase Example:  '3'
 *
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：n = 1
 * 输出：["()"]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 <= n <= 8
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        queue<tuple<string, int, int>> que;
        que.emplace("", 0, 0);
        while(!que.empty()) {
            auto [target, left, right] = que.front();
            que.pop();
            if (left != n) {
                que.emplace(target + "(", left + 1, right);
            }
            if (right < left) {
                que.emplace(target + ")", left, right + 1);
            }
            if (left == n && right == n) {
                res.emplace_back(target);
            }
        }

        return res;
    }
};
// @lc code=end

